package com.jxb.sort;

import java.util.Arrays;

/**
 * 归并排序
 * 递归调用，逻辑如下：
 *  1：结束条件，数组长度小于2
 *  2：进行递归分治
 *  3：对分治后的数组，进行各自排序
 *  4：进行合并排序
 *
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] nums = {11,4222,322,6,0,4,25,933,4,2,61};
        System.out.println("排序开始----------------->" + Arrays.toString(nums));
        int[] res = sortArray(nums);
        System.out.println("排序结束----------------->" + Arrays.toString(res));
    }

    public static int[] sortArray(int[] nums) {
        if (nums.length == 0) {
            return nums;
        }
        return partSort(nums);
    }

    private static Integer threshold = 3;

    private static int[] partSort(int[] partition) {
        if (partition.length <= threshold ) {
            return partition;
        }
        //进行分治
        int length = partition.length / 2;
        int[] left = Arrays.copyOfRange(partition,0,length);
        int[] right = Arrays.copyOfRange(partition,length,partition.length);
        //合并排序
        return sortP(partSort(left), partSort(right));
    }

    private static int[] sortP(int[] p1,int[] p2) {
        int[] res = new int[p1.length + p2.length];
        //若分治的大小不为1的话，需要对p1和p2进行各自排序
        if (threshold > 1) {
            sortSubArray(p1);
            sortSubArray(p2);
        }
        for (int index = 0, i = 0,j=0; index < res.length; index++) {
            //注意：判断语句需要使用if...else；光使用if语句当i或者j大于等于其数组长度，就会再次走到p1[i]>p2[j]的逻辑，此时会报下标越界异常
            //只有p2有数据
            if (i>= p1.length) {
                res[index] = p2[j];
                j++;
            }
            //只有p1有数据
            else if (j>= p2.length) {
                res[index] = p1[i];
                i++;
            }
            //p1的元素小于p2的元素
            else if (p1[i] > p2[j]) {
                res[index] = p2[j];
                j++;
            }else {
                //p2的元素小于p1的元素
                res[index] = p1[i];
                i++;
            }
        }
        return res;
    }

    private static void sortSubArray(int[] subArray) {
        //当前待排序的数据
        int currentValue;
        for (int i = 0;i<subArray.length-1;i++) {
           //已被排序的数据索引
            int preIndex = i;
            //获取当前需要排序的数据
            currentValue = subArray[preIndex + 1];
            while (preIndex >= 0 && currentValue<subArray[preIndex]) {
                //将已排序的数据向后移动一位
                subArray[preIndex + 1] = subArray[preIndex];
                preIndex--;
            }
            subArray[preIndex+1] = currentValue;
        }
    }

}
